/**
 * 链式存储解决了顺序存储删除和添加元素效率低的问题
 * 它的存储空间不是连续的，而使用指针指向下一元素，来表示逻辑关系
 * 
 * 优点：解决了顺序表的问题
 * 缺点：为了保存指针而花费了额外的空间
 */

 /**
  * 节点数据类型
  */
class Node {
    constructor (data, next = null) {
        this.data = data
        this.next = next
    }
}

/**
 * 单链表数据类型
 */
class Chain {
    /**
     * 初始化操作，创建一个带有头节点的空表
     */
    constructor () {
        let head = new Node()
        head.next = null
        if (head) { 
            this.data = head
        } else {
            throw new Error('create fail')
        }

        this.RANGE_ERROR = 'range_error'
        this.SUCCESS = 'success'
        this.FATAL = 'FATAL'
        this.FAIL = 'fail'
    }
    /**
     * 根据传递的参数创建一个单链表
     */
    create (eleList) {
        let status = this.RANGE_ERROR
        if (Array.isArray(eleList)) { 
            let p,q,n,i
            q = new Node() // 头节点
            n = eleList.length
            i = n - 1
            while (i >= 0) {
                p = new Node(eleList[i])
                p.next = q.next
                q.next = p
                i--
            }
            this.data = q
            status = this.SUCCESS
        }
        return status
    }
    /**
     * 按位置取值
     * @param {*} pos 下标 (从1开始)
     * @param {*} ele 获取值
     */
    retrieve (pos, ele) {
        let status = this.RANGE_ERROR
        let p = this.data.next // 第一个节点
        if (this.setPosition(pos, p) === 'success') {
            status = this.SUCCESS
            ele = p
        }
        console.log(p)
        return status
    }
    /**
     * 根据值查找位置
     * @param {*} val 
     * @param {*} pos 
     */
    locate (val, pos) {
        let status = this.RANGE_ERROR
        let p = this.data.next
        let i = 1
        while (p !== null) {
            if (p.data === val) break
            p = p.next
            i++
        }
        if (p) {
            pos = i
            status = this.SUCCESS
        }
        console.log(i)
        return status
    }
    /**
     * 返回第pos个节点的指针
     * @param {*} pos 
     * @param {*} p 
     */
    setPosition (pos, ptr = null) {
        let status = this.RANGE_ERROR
        let p = this.data

        let i = 0
        while (p && i < pos) {
            p = p.next
            i++
        }
        if (p && i === pos) {
            ptr = p  
            status = this.SUCCESS
        }
        return { status, ptr }
    } 
    /**
     * 在看指定的位置插入值
     * @param {*} pos 下标
     * @param {*} val 需要插入值
     */
    insert (pos, val) {
        let s
        let { status, ptr:p } = this.setPosition(pos - 1)
        if (status === 'success') {
            s = new Node()
            if (s) {
                s.data = val
                s.next = p.next
                p.next = s
            } else {
                status = this.FAIL
            }
        }
        return status
    }
    /**
     * 移除指定pos的节点
     * @param {*} pos 下标
     */
    remove (pos) {
        let { status, ptr:p } = this.setPosition(pos - 1)
        if (status === 'success') {
            let q = p.next
            p.next = q.next
            q = null
        }
        return status
    }
    /**
     * 清空链表，只保留头指针
     */
    clear () {
        let p = this.data,
            q = this.data.next
        while (q) {
            p.next = q.next
            q = null
            q = p.next
        }
    }
    /**
     * 销毁实例，清空所有数据包括头指针
     */
    destory () {
        this.clear()
        this.data = null
    }
    empty () {
        return this.data.next === null
    }
    size () {
        let i = 0,
            p = this.data.next
        while (p) {
            i++
            p = p.next
        }
        return length
    }
    /**
     * 求指定节点的前驱
     * @param {*} pos 下标
     */
    prior (pos, ele) {
        let {status, ptr:p } = this.setPosition(pos - 1)
        if (status === 'success') {
            ele = p
        }
        return status
    } 
    next (pos, ele) {
        let {status, ptr:p } = this.setPosition(pos + 1)
        if (status === 'success') {
            ele = p
        }
        return status
    }
    print () {
        console.log(this.data)
    }
}

let chainList = new Chain()
let res = chainList.create([1,2,3,4,5,6, 'hi'])
chainList.insert(1, 'ni')
console.log(JSON.stringify(chainList.data))
chainList.remove(2)
console.log(JSON.stringify(chainList.data))
